<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
           和题1区别：股票可以买卖多次, 有股票时，如果是今天买，必须dp[i - 1][1] - prices[i]和dp[i - 1][0]之间取一个
         * 输入：[7,1,5,3,6,4]
         * 输出：5
         * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
                 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
         * 
         * 输入: prices = [7,6,4,3,1]
         * 输出: 0
         * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
         * 
        */
        /* 
            时间：O(n) prices的长度
            空间：O(n) prices的长度，二维数组可以忽略不计
        */
        var maxProfit = function(prices) {
            const dp = new Array(prices.length).fill([0, 0])
            dp[0][0] = -prices[0]

            for (let i = 1; i < prices.length; i++) {
                dp[i] = [
                    Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]),
                    Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
                ]
            }
            console.log(dp, 'dp');
            return dp[prices.length - 1][1]
        };
        console.log(maxProfit([7,1,5,3,6,4]));
        // console.log(maxProfit([7,6,4,3,1]));
    </script>
</body>

</html>